﻿// Copyright (c) 2010 Dan Popick

// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:

// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;

namespace Open.Web.Stijl
{
    class JaggedBoundary
    {
        class PointComparer : IComparer<Point>
        {
            public int Compare(Point x, Point y)
            {
                return x.X - y.X;
            }

            public static PointComparer Instance = new PointComparer();
        }

        List<Point> _points;

        public Point Extent
        {
            get
            {
                return new Point(_points[0].Y, _points[_points.Count - 1].X);
            }
        }
        public double Area { get { return Extent.Area(); } }
        public IEnumerable<Point> Points { get { return _points; } }

        #region constructors
        public JaggedBoundary()
        {
            _points = new List<Point>(new Point[] { new Point(0, 0) });
        }

        public JaggedBoundary(IEnumerable<Point> points)
        {
            _points = new List<Point>(points);
        }

        public JaggedBoundary(JaggedBoundary boundary)
        {
            _points = new List<Point>(boundary._points);
        }
        #endregion

        /// <summary>
        /// Adds a block to the array, recalculating the points
        /// </summary>
        /// <param name="location">The target location for the block</param>
        /// <param name="width">The width of the block</param>
        /// <param name="height">The height of the block</param>
        public void AddRegion(Point location, int width, int height)
        {
            Size s = new Size(width, height);
            AddRegion(location, s);
        }

        /// <summary>
        /// Adds a block to the boundary, recalculating the points
        /// </summary>
        /// <param name="location">The target location for the block</param>
        /// <param name="size">The size of the block</param>
        public void AddRegion(Point location, Size size)
        {
            _points = new List<Point>(GetAlteredPoints(location, size));
        }

        /// <summary>
        /// Computes the cost of adding a block at each point in the array
        /// </summary>
        /// <param name="size">The size of the block to add</param>
        /// <returns>A list of doubles, indicating the cost of adding the block at each vertex</returns>
        public List<double> GetCostArray(Size size)
        {
            int lostSpace;
            int cleanCount;
            int increasedArea;
            return _points.Select((p, i) => // O(n^2)
            {
                double area = ((Point)size).Area();
                GetAdditionCost(i, size, out lostSpace, out cleanCount, out increasedArea); // O(n)
                return ((1 - (0.33 * (double)cleanCount)) * area) + lostSpace + increasedArea;
            }).ToList();
        }

        /// <summary>
        /// Computes the cost of adding a block at a given point in the array
        /// </summary>
        /// <param name="index">The index of the point/vertex in the array</param>
        /// <param name="size">Size of the block to add</param>
        /// <param name="lostSpace">Space lost as a result of adding the block</param>
        /// <param name="cleanCount">The number of "clean" matches -- that is, if placed block hits any vertices other than the origin</param>
        /// <param name="increasedSpace">total amount of increased space for the entire outside block</param>
        void GetAdditionCost(int index, Size size, out int lostSpace, out int cleanCount, out int increasedSpace)
        {
            Point startPoint = _points[index];
            Point offset = startPoint + size;
            double initialBoundingArea = this.Area;

            // start at the point before the placement point and iterate back until
            // the current point Y exceeds the offset Y
            cleanCount = 0;
            int i = index - 1;
            int lostSpaceLeft = 0;
            while (i >= 0 && _points[i].Y < offset.Y)
            {
                int lostY = offset.Y - _points[i].Y;
                int width = _points[i + 1].X - _points[i].X;
                lostSpaceLeft += lostY * width;

                i--;
            }

            if (lostSpaceLeft == 0 && (i < 0 || _points[i].Y == offset.Y))
                cleanCount++;

            // start at the point after the placement point and iterate until the point 
            // exceeds the offset X
            int lostSpaceRight = 0;
            i = index + 1;
            while (i < _points.Count && _points[i].X < offset.X)
            {
                int lostY = startPoint.Y - _points[i].Y;
                int width;

                // we're computing the X-distance between the current point and the next point,
                // or the current point and the offset point, whichever's closer.
                if (_points.Count - 1 == i)
                    width = offset.X - _points[i].X;
                else
                    width = Math.Min(_points[i + 1].X, offset.X) - _points[i].X;

                lostSpaceRight += lostY * width;

                i++;
            }

            if (lostSpaceRight == 0 && (i >= _points.Count || _points[i].X == offset.X))
                cleanCount++;

            int newHeight = Math.Max(_points[0].Y, offset.Y);
            int newWidth = Math.Max(_points[_points.Count - 1].X, offset.X);
            double finalBoundingArea = newHeight * newWidth;

            lostSpace = lostSpaceLeft + lostSpaceRight;
            increasedSpace = (int)(finalBoundingArea - initialBoundingArea);
        }

        /// <summary>
        /// Adjusts the array to accomodate a new block in the array
        /// </summary>
        /// <param name="location">The point at which the new block is added</param>
        /// <param name="size">Size of the block</param>
        /// <returns>A new set of jagged boundary points adjusted to accomodate the block</returns>
        IEnumerable<Point> GetAlteredPoints(Point location, Size size)
        {
            Point upperLeft = new Point(location.X, location.Y + size.Height);
            Point lowerRight = new Point(location.X + size.Width, location.Y);

            int idx = 0;
            while (_points[idx].Y > upperLeft.Y)
                yield return _points[idx++];

            if (_points[idx].Y < upperLeft.Y)
                yield return new Point(_points[idx].X, upperLeft.Y);
            else if (_points[idx].Y == upperLeft.Y)
                yield return _points[idx];

            while (idx < _points.Count && _points[idx].X <= lowerRight.X)
                idx++;

            if (idx == _points.Count)
                yield return new Point(lowerRight.X, 0);
            else
            {
                yield return new Point(lowerRight.X, _points[idx - 1].Y);

                while (idx < _points.Count)
                    yield return _points[idx++];
            }
        }
    }
}
